package SumOfTwoNumbers;

import java.util.HashMap;
import java.util.Map;


/*
给定一个整数数组 nums 和一个整数目标值 target，
请你在该数组中找出 和为目标值 target  的那 两个 整数，
并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，
数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。*/

public class Solution {


    /*解题思路：

    创建一个哈希表 (numToIndex) 用于存储数组元素与它们的索引。
    遍历数组 nums，对于每个元素 nums[i]，计算其差值
    complement = target - nums[i]，这个差值代表了需要与当前元素相加得到目标值
    target 的另一个元素。
    检查哈希表中是否存在 complement，如果存在，说明已经找到了两个元素的和等于目标值
    target，返回它们的索引。
    如果哈希表中不存在 complement，则将当前元素及其索引添加到哈希表中。
    如果遍历完整个数组都没有找到匹配的元素，最后返回一个空数组表示无法找到解。
    这个算法具有线性时间复杂度 O(n)，因为只需要一次遍历数组。
    哈希表用于存储元素和索引的映射，能够快速查找元素，因此是解决这个问题的有效方法。*/
    public static int[] twoSum(int[] nums, int target) {
        // 创建一个哈希表用于存储数组元素与它们的索引
        Map<Integer, Integer> numToIndex = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            // 检查是否存在与当前元素匹配的元素，如果存在，返回它们的索引
            if (numToIndex.containsKey(complement)) {
                return new int[]{numToIndex.get(complement), i};
            }
            // 否则，将当前元素及其索引添加到哈希表中
            numToIndex.put(nums[i], i);
        }

        // 如果没有找到匹配的元素，返回一个空数组
        return new int[]{};
    }
}
